package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhenzicheng
 * @date 2022-06-27 11:51
 */
public class BinaryTreeLevelOrderTraversal_102 {

  /*BFS广度优先搜索*/
  public List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();

    if (root == null) return result;

    // 根节点入队
    queue.offer(root);
    while (!queue.isEmpty()) {
      // 每层节点数
      int levelCount = queue.size();
      // 每层节点
      List<Integer> subList = new ArrayList<>();
      // 处理本层
      for (int i = 0; i < levelCount; i++) {
        // 有左节点就入队
        if (queue.peek().left != null) queue.offer(queue.peek().left);
        // 有右节点就入队
        if (queue.peek().right != null) queue.offer(queue.peek().right);
        // 真正读取
        subList.add(queue.poll().val);
      }
      result.add(subList); // 保存本层
    }
    return result;
  }


}
